<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title>TypeSet</title>
		<link rel="stylesheet" href="main.css"/>
		<style>
			.example {
				margin: 1.35em auto;
				text-align: center;
			}

			.example {
				font-family: 'times new roman', 'FreeSerif', serif;
				font-size: 14px;
				line-height: 21px;
			}

			.example ul {
				display: inline-block;
				list-style-type: none;
				padding: 0 0 0 1.5em;
				margin: 0 auto 0 0;
				text-align: right;
			}

			#browser, #browser-assist {
				text-align: justify;
				width: 350px;
				margin: 0 0 0 auto;
				display: inline-block;
				font-family: 'times new roman', 'FreeSerif', serif;
				font-size: 14px;
				line-height: 21px;
			}
		</style>
	</head>
	<body>
		<h1><span class="tex">T<sub>e</sub>X</span> line breaking algorithm in JavaScript</h1>
		<p class="subtitle">Bram Stein (<a href="http://www.bramstein.com/">http://www.bramstein.com</a> - <a href="mailto:b.l.stein@gmail.com">b.l.stein@gmail.com</a>)</p>

		<p>This is an implementation of the <a href="http://www3.interscience.wiley.com/journal/113445055/abstract">Knuth and Plass line breaking algorithm</a> using JavaScript and the HTML5 canvas element. The goal of this implementation is to optimally set justified text in the new HTML5 canvas element, and ultimately provide a library for various line breaking algorithms in JavaScript.</p>
		<p>The paragraph below is set using a JavaScript implementation of the classic Knuth and Plass algorithm as used in <span class="tex">T<sub>e</sub>X</span>. The numbers on the right of each line are the stretching or shrinking ratio compared to the optimal line width. This example uses a default space of <sup>1</sup>⁄<sub>3</sub> em, with a stretchability and shrink-ability of <sup>1</sup>⁄<sub>6</sub> em and <sup>1</sup>⁄<sub>9</sub> em respectively.</p>
        <div class="example"><img src="typeset-with-ratio.png"></div>
		<p>The following paragraph is set by your browser using <code>text-align: justify</code>. Notice the lines in the paragraph set by your browser have, on average, greater inter-word spacing than the canvas version, which is successful at minimizing the inter-word spacing over all lines.</p>
		<div class="example"><div id="browser"></div></div>
		<p>Your browser also ends up with ten lines instead of the nine lines found by the Knuth and Plass line breaking algorithm. This comparison might not be completely fair since we don't know the default inter-word space used by the browser (nor its stretching and shrinking parameters.) Experimental results however indicate the values used in most browsers are either identical or very similar. The next section explains how the ratio values for your browser were calculated.</p>

		<h2>Measuring the quality of browser line breaks</h2>
		<p>Unfortunately there is no API to retrieve the positions of the line breaks the browser inserted, so we'll have to resort to some trickery. By wrapping each word in an invisible <code>&lt;span&gt;</code> element and retrieving its <code>y</code> position we can find out when a new line starts. If the <code>y</code> position of the current word is different from the previous word we know a new line has started. This way a paragraph is split up in several individual lines.</p>

		<p>The ratios are then calculated by measuring the difference between the width of each line when <code>text-align</code> is set to <code>justify</code> and when it is set to <code>left</code>. This difference is then divided by the amount of stretchability of the line: i.e. the number of spaces multiplied by the stretch width for spaces. Although we don't know the actual stretchability we can use <sup>1</sup>⁄<sub>6</sub> em, just like the Knuth and Plass algorithm, if we only use it for comparison.</p>


		<h2>Assisted browser line breaks</h2>
		<p>The following paragraph is set according to the line breaks found by the Knuth and Plass algorithm, but instead of using the HTML5 Canvas element it is rendered by your browser. By adjusting the CSS <code>word-spacing</code> property we have achieved the same paragraph as in the Canvas example.</p>
		<div class="example"><div id="browser-assist" style="white-space: normal;"></div></div>

		<h2>Examples</h2>
		<p>The line breaking algorithm is not only capable of justifying text, it can perform all sorts of alignment with an appropriate selection of boxes, glue and penalties. It is also possible to give it varying line widths to flow text around illustrations, asides or quotes. Alternatively, varying line widths can be used to create interesting text shapes as demonstrated below.</p>
		<h3>Ragged right and centered alignment</h3>
		<p>The following example is set ragged right. Ragged right is not simply justified text with fixed width inter-word spacing. Instead the algorithm tries to minimize the amount of white space at the end of each sentence over the whole paragraph. It also attempts to reduce the number of words that are "sticking out" of the margin. It is very noticeable here that hyphenation could improve the ragged right setting greatly by, for example, hyphenating the word "lime-tree".</p>
		<canvas id="left" width="350" height="210"></canvas>
		<p>Ragged left text can be achieved by using a ragged right text and aligning its line endings with the left border. The example below is set centered. Again this is not simply a centering of justified text, but instead an attempt at minimizing the line lengths over the whole paragraph.</p>
		<canvas id="center" width="350" height="210"></canvas>
		<h3>Variable line width</h3>
		<p>By varying the line width for a paragraph it is possible to flow the text around illustrations, asides, quotes and such. The example below leaves a gap for an illustration by setting the line widths temporarily shorter and then reverting.</p>
		<canvas id="flow" width="350" height="280"></canvas>
		<p>It is also possible to make some non-rectangular shapes, as shown in the example below. This text is laid out using an increasing line width and center aligning each line.</p>
		<canvas id="triangle" width="600" height="240"></canvas>
    <canvas id="circle" width="600" height="300"></canvas>

		<h2>To-do</h2>
		<p>The following are some extensions to the algorithm discussed in the original paper, which I intend to implement (at some point.)</p>
		<ul>
			<li><a href="http://en.wikipedia.org/wiki/Hanging_punctuation">Hanging punctuation</a>. The following quote from the original paper explains how to implement it using the box, glue and penalty model:

				<blockquote>Some people prefer to have the right edge of their text look ‘solid’, by setting periods,
				commas, and other punctuation marks (including inserted hyphens) in the right-hand
				margin. For example, this practice is occasionally used in contemporary advertising.
				It is easy to get inserted hyphens into the margin: We simply let the width of the
				corresponding penalty item be zero. And it is almost as easy to do the same for periods
				and other symbols, by putting every such character in a box of width zero and adding
				the actual symbol width to the glue that follows. If no break occurs at this glue, the
				accumulated width is the same as before; and if a break does occur, the line will be
				justified as if the period or other symbol were not present.</blockquote>
			</li>
			<li>Test in more browsers. Currently working are: Firefox/Linux, Firefox/Windows, Safari/OSX, Safari/Windows, Chrome/Linux and Chrome/Windows. Firefox on OSX, however doesn't perform as well due to different default fonts (or font sizes.)</li>
			<li>Compare quality against line-breaking implemented by <a href="http://msdn.microsoft.com/en-us/library/ms534671%28VS.85%29.aspx">Internet Explorer's <code>text-justify</code> CSS property</a>.</li>
			<li>Figure out how to deal with dynamic paragraphs (i.e. paragraphs being edited) as their ratios will change during editing and thus visibly move around.</li>
		</ul>

		<h2>Source code</h2>
		<ul>
			<li><a href="../../src/linebreak.js">linebreak.js</a> (main algorithm, drawing functions are in this document.)</li>
			<li><a href="../../src/formatter.js">formatter.js</a> (code to turn text into node lists with appropriate glue and penalties)</li>
		</ul>
		<h2>References</h2>
		<p>These are the resources I found most useful while implementing the line breaking algorithm.</p>
		<ul>
			<li><a href="http://www.amazon.com/Digital-Typography-Center-Language-Information/dp/1575860104/">Digital Typography, Donald E. Knuth</a></li>
			<li><a href="http://www3.interscience.wiley.com/journal/113445055/abstract">Breaking paragraphs into lines, Donald E. Knuth, Michael F. Plass</a></li>
			<li><a href="http://defoe.sourceforge.net/folio/knuth-plass.html">Knuth &amp; Plass line-breaking Revisited</a></li>
			<li><a href="http://en.wikipedia.org/w/index.php?title=Word_wrap">Wikipedia: Word wrap</a></li>
		</ul>

		<span style="font-family: sans-serif; font-size: 12px;" id="test">&nbsp;</span>

		<script type="text/javascript" src="../../lib/jquery-1.4.2.js"></script>
    <script type="text/javascript" src="../../src/linked-list.js"></script>
		<script type="text/javascript" src="../../src/linebreak.js"></script>
		<script type="text/javascript" src="../../src/formatter.js"></script>
		<script type="text/javascript" src="../../lib/hypher.js"></script>
		<script type="text/javascript" src="../../lib/en-us.js"></script>
		<script type="text/javascript" src="browser.js"></script>
		<script type="text/javascript" src="browser-assist.js"></script>
		<script type="text/javascript">
			var text = "In olden times when wishing still helped one, there lived a king whose daughters were all beautiful; and the youngest was so beautiful that the sun itself, which has seen so much, was astonished whenever it shone in her face. Close by the king's castle lay a great dark forest, and under an old lime-tree in the forest was a well, and when the day was very warm, the king's child went out to the forest and sat down by the fountain; and when she was bored she took a golden ball, and threw it up on high and caught it; and this ball was her favorite plaything."

			function draw(context, nodes, breaks, lineLengths, center) {
				var i = 0, lines = [], point, j, r, lineStart = 0, y = 4, maxLength = Math.max.apply(null, lineLengths);

				// Iterate through the line breaks, and split the nodes at the
				// correct point.
				for (i = 1; i < breaks.length; i += 1) {
					point = breaks[i].position,
					r = breaks[i].ratio;

					for (var j = lineStart; j < nodes.length; j += 1) {
						// After a line break, we skip any nodes unless they are boxes or forced breaks.
						if (nodes[j].type === 'box' || (nodes[j].type === 'penalty' && nodes[j].penalty === -Typeset.linebreak.infinity)) {
							lineStart = j;
							break;
						}
					}
					lines.push({ratio: r, nodes: nodes.slice(lineStart, point + 1), position: point});
					lineStart = point;
				}

				lines.forEach(function (line, lineIndex) {
					var x = 0, lineLength = lineIndex < lineLengths.length ? lineLengths[lineIndex] : lineLengths[lineLengths.length - 1];

					if (center) {
						x += (maxLength - lineLength) / 2;
					}

					line.nodes.forEach(function (node, index, array) {
						if (node.type === 'box') {
							context.fillText(node.value, x, y);
							x += node.width;
						} else if (node.type === 'glue') {
							x += node.width + line.ratio * (line.ratio < 0 ? node.shrink : node.stretch);
						} else if (node.type === 'penalty' && node.penalty === 100 && index === array.length - 1) {
                            context.fillText('-', x, y);
                        }
					});

                    // move lower to draw the next line
					y += 21;
				});
            };

			jQuery(function ($) {
				function align(identifier, type, lineLengths, tolerance, center) {
					var canvas = $(identifier).get(0),
                    context = canvas.getContext && canvas.getContext('2d'),
                    format, nodes, breaks;
					if (context) {
						context.textBaseline = 'top';
						context.font = "14px 'times new roman', 'FreeSerif', serif";

						format = Typeset.formatter(function (str) {
							return context.measureText(str).width;
						});

						nodes = format[type](text);

						breaks = Typeset.linebreak(nodes, lineLengths, {tolerance: tolerance});

						if (breaks.length !== 0) {
							draw(context, nodes, breaks, lineLengths, center);
						} else {
							context.fillText('Paragraph can not be set with the given tolerance.', 0, 0);
						}
					}
					return [];
				}

                var r = [],
                    radius = 147;

                for (var j = 0; j < radius * 2; j += 21) {
                    r.push(Math.round(Math.sqrt((radius - j / 2) * (8 * j))));
                }

                r = r.filter(function (v) {
                    return v > 30;
                });

				align('#center',   'center',  [350], 3);
				align('#left',     'left',    [350], 4);
				align('#flow',     'justify', [350, 350, 350, 200, 200, 200, 200, 200, 200, 200, 350, 350], 3);
				align('#triangle', 'justify', [50, 100, 150, 200, 250, 300, 350, 400, 450, 500, 550], 3, true);
                align('#circle',   'justify', r, 3, true);
			});
		</script>

		<!-- Google Analytics -->
		<script type="text/javascript">
			var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
			document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
		</script>
		<script type="text/javascript">
			try {
				var pageTracker = _gat._getTracker("UA-10076742-1");
				pageTracker._trackPageview();
			} catch(err) {
			}
		</script>
	</body>
</html>
